package sort;


import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author dx
 * @version 1.0
 * @date 2022/3/23 14:26
 * @description:给定一个包含[0,n]中n个数的数组nums,找出[0,n]这个范围内没有出现在数组中的那个数
 * 例如：
 * 输入 nums = [3,0,1]  ----->  2
 * 输入 nums = [0,1]  -------> 2
 * 输入nums = [0]     -------> 1
 */
public class Lost_num {

    public static void main(String []args){
        int test1[] = {0,1,2,3,5,4,7,8,9};
        int test = missingNumber(test1);
        System.out.println(test);
        System.out.println(missingNumber2(test1));
    }

    //方法1：排序后 与下标进行对比
    public static int missingNumber(int[] nums){

        int len = nums.length;
        Arrays.sort(nums);
        for(int i=0;i<len;i++){
            if(nums[i]!=i)
                return i;
        }
        return len;

    }
    //方法2：将数组元素放到Set集合中，然后从0-{n遍历集合是否存在0-n
    public static int missingNumber2(int[] nums){

        Set<Integer> set = new HashSet<>();
        for(int num : nums){
            set.add(num);
        }
        for(int i=0;i<nums.length;i++){
            if(!set.contains(i)){
                return i;
            }
        }
        return nums.length;
    }
    //方法3：异或的方法
//    public static int missingNumber3(int[] nums){
//
//    }
}
